home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / lisp / kcl / akcl / kcl.lha / c / big.c < prev    next >
C/C++ Source or Header  |  1987-06-04  |  17KB  |  951 lines
  1. /*
  2. (c) Copyright Taiichi Yuasa and Masami Hagiya, 1984.  All rights reserved.
  3. Copying of this file is authorized to users who have executed the true and
  4. proper "License Agreement for Kyoto Common LISP" with SIGLISP.
  5. */
  6.  
  7. /*
  8.     big.c
  9.  
  10.     bignum routines
  11. */
  12.  
  13. #include "include.h"
  14. #include "num_include.h"
  15.  
  16. struct bignum *
  17. stretch_big(x, i)
  18. struct bignum *x;
  19. int i;
  20. {
  21.     /*  We assume that x is already pushed on the value stack.  */
  22.     x->big_cdr = (struct bignum *)alloc_object(t_bignum);
  23.     x = x->big_cdr;
  24.     x->big_car = i;
  25.     x->big_cdr = NULL;
  26.     return(x);
  27. }
  28.  
  29. struct bignum *
  30. copy_big(x)
  31. struct bignum *x;
  32. {
  33.     struct bignum *y0, *y;
  34.         vs_mark;
  35.     
  36. /*    vs_push((object)x);    */
  37.     y0 = y = (struct bignum *)alloc_object(t_bignum);
  38.     y->big_car = x->big_car;
  39.     y->big_cdr = NULL;
  40.         /*  For GBC not to go mad.  */
  41.     vs_push((object)y);
  42.         /*  Saving for GBC.  */
  43.     for (x = x->big_cdr;  x != NULL;  x = x->big_cdr)
  44.         y = stretch_big(y, x->big_car);
  45.     vs_reset;
  46.     return(y0);
  47. }
  48.  
  49. struct bignum *
  50. copy_to_big(x)
  51. object    x;
  52. {
  53.     struct bignum *y;
  54.  
  55.     if (type_of(x) == t_fixnum) {
  56.         y = (struct bignum *)alloc_object(t_bignum);
  57.         y->big_car = fix(x);
  58.         y->big_cdr = NULL;
  59.     } else if (type_of(x) == t_bignum)
  60.         y = copy_big(x);
  61.     else
  62.         FEerror("integer expected",0);
  63.     return(y);
  64. }
  65.  
  66. /*
  67.     Big_zerop(x) answers if bignum x is zero or not.
  68.     X may be any bignum.
  69. */
  70. big_zerop(x)
  71. struct bignum *x;
  72. {
  73.     for (;;)
  74.         if (x->big_car != 0)
  75.             return(0);
  76.         else if ((x = x->big_cdr) == NULL)
  77.             return(1);
  78. }
  79.  
  80. /*
  81.     Big_sign(x) returns
  82.         something < -1    if x < -1
  83.         -1        if x = -1
  84.         0        if x = 0
  85.         something > 0    if x > 0.
  86.     X may be any bignum.
  87. */
  88. int
  89. big_sign(x)
  90. struct bignum *x;
  91. {
  92.     struct bignum *l;
  93.     bool zero;
  94.     bool minus1;
  95.  
  96.     l = x;
  97.     zero = minus1 = TRUE;
  98.     for (;;) {
  99.         if (l->big_cdr == NULL) {
  100.             if (l->big_car == 0) {
  101.                 if (zero)
  102.                     return(0);
  103.                 else
  104.                     return(1);
  105.             }
  106.             if (l->big_car == -1) {
  107.                 if (minus1)
  108.                     return(-1);
  109.                 else
  110.                     return(-2);
  111.             }
  112.             if (l->big_car < 0)
  113.                 return(-3);
  114.             else
  115.                 return(3);
  116.             /*  return(l->big_car);  */
  117.         }
  118.         if (l->big_car != 0)
  119.             zero = FALSE;
  120.         if (l->big_car != 0x7fffffff)
  121.             minus1 = FALSE;
  122.         l = l->big_cdr;
  123.     }
  124. }
  125.  
  126. /*
  127. int
  128. big_sign(x)
  129. struct bignum *x;
  130. {
  131.     int i;
  132.  
  133.     if (x->big_cdr == NULL)
  134.         return(x->big_car);
  135.     i = big_sign(x->big_cdr);
  136.     if (i == 0)
  137.         return(x->big_car);
  138.     if (i == -1)
  139.         return(x->big_car | ~MASK);
  140.     return(i);
  141. }
  142. */
  143.  
  144. /*
  145.     Big_compare(x, y) returns
  146.         -1    if x < y
  147.         0    if x = y
  148.         1    if x > y.
  149.     X and y may be any bignum.
  150. */
  151. int
  152. big_compare(x, y)
  153. struct bignum *x, *y;
  154. {
  155.     int i;
  156.     int comparison;
  157.  
  158.     comparison = 0;
  159.  
  160. LOOP:
  161.     if (x->big_cdr == NULL)
  162.         if (y->big_cdr == NULL)
  163.             if (x->big_car < y->big_car)
  164.                 return(-1);
  165.             else if (x->big_car == y->big_car)
  166.                 return(comparison);
  167.             else
  168.                 return(1);
  169.         else if ((i = big_sign(y->big_cdr)) == 0)
  170.             if (x->big_car < y->big_car)
  171.                 return(-1);
  172.             else if (x->big_car == y->big_car)
  173.                 return(comparison);
  174.             else
  175.                 return(1);
  176.         else if (i == -1)
  177.             if (x->big_car < (y->big_car|~MASK))
  178.                 return(-1);
  179.             else if (x->big_car == (y->big_car|~MASK))
  180.                 return(comparison);
  181.             else
  182.                 return(1);
  183.         else if (i > 0)
  184.             return(-1);
  185.         else
  186.             return(1);
  187.     else if (y->big_cdr == NULL)
  188.         if ((i = big_sign(x->big_cdr)) == 0)
  189.             if (x->big_car < y->big_car)
  190.                 return(-1);
  191.             else if (x->big_car == y->big_car)
  192.                 return(comparison);
  193.             else
  194.                 return(1);
  195.         else if (i == -1)
  196.             if ((x->big_car|~MASK) < y->big_car)
  197.                 return(-1);
  198.             else if ((x->big_car|~MASK) == y->big_car)
  199.                 return(comparison);
  200.             else
  201.                 return(1);
  202.         else if (i < 0)
  203.             return(-1);
  204.         else
  205.             return(1);
  206.     else {
  207.         if (x->big_car < y->big_car)
  208.             comparison = -1;
  209.         else if (x->big_car == y->big_car)
  210.             ;
  211.         else
  212.             comparison = 1;
  213.         x = x->big_cdr;
  214.         y = y->big_cdr;
  215.         goto LOOP;
  216.     }
  217. }
  218.  
  219. /*
  220. int
  221. big_compare(x, y)
  222. struct bignum *x, *y;
  223. {
  224.     int i;
  225.  
  226.     if (x->big_cdr == NULL)
  227.         if (y->big_cdr == NULL)
  228.             if (x->big_car < y->big_car)
  229.                 return(-1);
  230.             else if (x->big_car == y->big_car)
  231.                 return(0);
  232.             else
  233.                 return(1);
  234.         else if ((i = big_sign(y->big_cdr)) == 0)
  235.             if (x->big_car < y->big_car)
  236.                 return(-1);
  237.             else if (x->big_car == y->big_car)
  238.                 return(0);
  239.             else
  240.                 return(1);
  241.         else if (i == -1)
  242.             if (x->big_car < (y->big_car|~MASK))
  243.                 return(-1);
  244.             else if (x->big_car == (y->big_car|~MASK))
  245.                 return(0);
  246.             else
  247.                 return(1);
  248.         else if (i > 0)
  249.             return(-1);
  250.         else
  251.             return(1);
  252.     else if (y->big_cdr == NULL)
  253.         if ((i = big_sign(x->big_cdr)) == 0)
  254.             if (x->big_car < y->big_car)
  255.                 return(-1);
  256.             else if (x->big_car == y->big_car)
  257.                 return(0);
  258.             else
  259.                 return(1);
  260.         else if (i == -1)
  261.             if ((x->big_car|~MASK) < y->big_car)
  262.                 return(-1);
  263.             else if ((x->big_car|~MASK) == y->big_car)
  264.                 return(0);
  265.             else
  266.                 return(1);
  267.         else if (i < 0)
  268.             return(-1);
  269.         else
  270.             return(1);
  271.     else if ((i = big_compare(x->big_cdr, y->big_cdr)) == 0)
  272.         if (x->big_car < y->big_car)
  273.             return(-1);
  274.         else if (x->big_car == y->big_car)
  275.             return(0);
  276.         else
  277.             return(1);
  278.     else
  279.         return(i);
  280. }
  281. */
  282.  
  283. /*
  284.     Complement_big(x) destructively takes
  285.     the complement of bignum x.
  286.     X may be any bignum.
  287. */
  288. complement_big(x)
  289. struct bignum *x;
  290. {
  291. /*    vs_mark;
  292.  
  293.     vs_push((object)x);    */
  294.     while (x->big_cdr != NULL) {
  295.         if (x->big_car != 0) {
  296.             x->big_car = (-(x->big_car)) & MASK;
  297.             goto ONE;
  298.         }
  299.         x = x->big_cdr;
  300.     }
  301.     if (x->big_car == ~MASK) {
  302.         x->big_car = 0;
  303.         stretch_big(x, 1);
  304.     } else
  305.         x->big_car = -(x->big_car);
  306. /*    vs_reset;    */
  307.     return;
  308.  
  309. ONE:
  310.     for (;;) {
  311.         x = x->big_cdr;
  312.         if (x->big_cdr == NULL)
  313.             break;
  314.         x->big_car = (~(x->big_car)) & MASK;
  315.     }
  316.     x->big_car = ~(x->big_car);
  317. /*    vs_reset;    */
  318.     return;
  319. }
  320.  
  321. /*
  322.     big_minus(x) returns the complement of bignum x.
  323.     X may be any bignum.
  324. */
  325. struct bignum *
  326. big_minus(x)
  327. struct bignum *x;
  328. {
  329.     struct bignum *y0, *y;
  330.     vs_mark;
  331.  
  332. /*    vs_push((object)x);    */
  333.     y = y0 = (struct bignum *)alloc_object(t_bignum);
  334.     y0->big_car = 0;
  335.     y0->big_cdr = NULL;
  336.     vs_push((object)y0);
  337.     while (x->big_cdr != NULL) {
  338.         if (x->big_car != 0) {
  339.             y->big_car = (-(x->big_car)) & MASK;
  340.             goto ONE;
  341.         }
  342.         x = x->big_cdr;
  343.         y = stretch_big(y, 0);
  344.     }
  345.     if (x->big_car == ~MASK) {
  346.         y->big_car = 0;
  347.         stretch_big(y, 1);
  348.     } else
  349.         y->big_car = -(x->big_car);
  350.     vs_reset;
  351.     return(y0);
  352.  
  353. ONE:
  354.     for (;;) {
  355.         x = x->big_cdr;
  356.         y = stretch_big(y, 0);
  357.         if (x->big_cdr == NULL)
  358.             break;
  359.         y->big_car = (~(x->big_car)) & MASK;
  360.     }
  361.     y->big_car = ~(x->big_car);
  362.     vs_reset;
  363.     return(y0);
  364. }
  365.  
  366. /*
  367.     Add_int_big(i, x) destructively adds non-negative int i
  368.     to bignum x.
  369.     I should be non-negative.
  370.     X may be any bignum.
  371. */
  372. add_int_big(i, x)
  373. int i;
  374. struct bignum *x;
  375. {
  376. /*    vs_mark;
  377.  
  378.     vs_push((object)x);    */
  379.     while (x->big_cdr != NULL) {
  380.         x->big_car += i;
  381.         if (x->big_car < 0) {
  382.             /*  carry  */
  383.             i = 1;
  384.             x->big_car &= MASK;
  385.         } else {
  386.         /*    vs_reset;    */
  387.             return;
  388.         }
  389.         x = x->big_cdr;
  390.     }
  391.     if (x->big_car >= 0) {
  392.         x->big_car += i;
  393.         if (x->big_car < 0) {
  394.             /*  overflow  */
  395.             x->big_car &= MASK;
  396.             stretch_big(x, 1);
  397.         }
  398.     } else
  399.         x->big_car += i;
  400. /*    vs_reset;    */
  401.     return;
  402. }
  403.  
  404. /*
  405.     Sub_int_big(i, x) destructively subtracts non-negative int i
  406.     from bignum x.
  407.     I should be non-negative.
  408.     X may be any bignum.
  409. */
  410. sub_int_big(i, x)
  411. int i;
  412. struct bignum *x;
  413. {
  414. /*    vs_mark;
  415.  
  416.     vs_push((object)x);    */
  417.     while (x->big_cdr != NULL) {
  418.         x->big_car -= i;
  419.         if (x->big_car < 0) {
  420.             /*  borrow  */
  421.             i = 1;
  422.             x->big_car &= MASK;
  423.         } else {
  424.         /*    vs_reset;    */
  425.             return;
  426.         }
  427.         x = x->big_cdr;
  428.     }
  429.     if (x->big_car < 0) {
  430.         /*  overflow  */
  431.         x->big_car -= i;
  432.         if (x->big_car >= 0) {
  433.             x->big_car &= MASK;
  434.             stretch_big(x, -2);
  435.         }
  436.     } else
  437.         x->big_car -= i;
  438. /*    vs_reset;    */
  439.     return;
  440. }
  441.  
  442. /*
  443.     Mul_int_big(i, x) destructively multiplies non-negative bignum x
  444.     by non-negative int i.
  445.     I should be non-negative.
  446.     X should be non-negative.
  447. */
  448. mul_int_big(i, x)
  449. int i;
  450. struct bignum *x;
  451. {
  452.     int h;
  453. /*    vs_mark;
  454.  
  455.     vs_push((object)x);    */
  456.     h = 0;
  457.     for (;;) {
  458.         extended_mul(i, x->big_car, h, &h, &(x->big_car));
  459.         if (x->big_cdr == NULL)
  460.             break;
  461.         x = x->big_cdr;
  462.     }
  463.     if (h > 0)
  464.         stretch_big(x, h);
  465. /*    vs_reset;    */
  466.     return;
  467. }
  468.  
  469. /*
  470.     Div_int_big(i, x) destructively divides non-negative bignum x
  471.     by positive int i.
  472.     X will hold the remainder of the division.
  473.     Div_int_big(i, x) returns the remainder of the division.
  474.     I should be positive.
  475.     X should be non-negative.
  476. */
  477. int
  478. div_int_big(i, x)
  479. int i;
  480. struct bignum *x;
  481. {
  482.     int r;
  483.  
  484.     if (i == 0)
  485.         FEerror("0 divizer",0);
  486.     if (x->big_cdr == NULL) {
  487.         r = x->big_car%i;
  488.         x->big_car /= i;
  489.         return(r);
  490.     }
  491.     r = div_int_big(i, x->big_cdr);
  492.     extended_div(i, r, x->big_car, &(x->big_car), &r);
  493.     return(r);
  494. }
  495.  
  496. /*
  497.     Big_plus(x, y) returns the sum of bignum x and bignum y.
  498.     X and y may be any bignum.
  499. */
  500. struct bignum *
  501. big_plus(x, y)
  502. struct bignum *x, *y;
  503. {
  504.     struct bignum *z0, *z;
  505.     int c;
  506.     vs_mark;
  507.  
  508. /*    vs_push((object)x);
  509.     vs_push((object)y);    */
  510.     z0 = z = (struct bignum *)alloc_object(t_bignum);
  511.     z->big_car = 0;
  512.     z->big_cdr = NULL;
  513.     vs_push((object)z);
  514.     c = 0;
  515.     for (;;) {
  516.         z->big_car = x->big_car + y->big_car + c;
  517.         if (x->big_cdr == NULL)
  518.             if (y->big_cdr == NULL)
  519.                 goto BOTH_END;
  520.             else
  521.                 goto X_END;
  522.         else if (y->big_cdr == NULL)
  523.             goto Y_END;
  524.         else
  525.             ;
  526.         if (z->big_car < 0) {
  527.             c = 1;
  528.             z->big_car &= MASK;
  529.         } else
  530.             c = 0;
  531.         x = x->big_cdr;
  532.         y = y->big_cdr;
  533.         z = stretch_big(z, 0);
  534.     }
  535.  
  536. BOTH_END:
  537.     if (x->big_car>=0 && y->big_car>=0 && z->big_car<0) {
  538.         z->big_car &= MASK;
  539.         stretch_big(z, 1);
  540.     } else if (x->big_car<0 && y->big_car<0 && z->big_car>=0) {
  541.         stretch_big(z, -2);
  542.     }
  543.     vs_reset;
  544.     return(z0);
  545.  
  546. X_END:
  547.     if (x->big_car >= 0)
  548.         c = 1;
  549.     else
  550.         c = -1;
  551.     for (;;) {
  552.         if (z->big_car < 0)
  553.             z->big_car &= MASK;
  554.         else {
  555.             z->big_cdr = y->big_cdr;
  556.             vs_reset;
  557.             return(z0);
  558.         }
  559.         y = y->big_cdr;
  560.         z = stretch_big(z, 0);
  561.         z->big_car = y->big_car + c;
  562.         if (y->big_cdr == NULL) {
  563.             if (c>=0&&y->big_car>=0&&z->big_car<0) {
  564.                 z->big_car &= MASK;
  565.                 stretch_big(z, 1);
  566.             } else if (c<0&&y->big_car<0&&z->big_car>=0) {
  567.                 stretch_big(z, -2);
  568.             }
  569.             vs_reset;
  570.             return(z0);
  571.         }
  572.     }
  573.  
  574. Y_END:
  575.     if (y->big_car >= 0)
  576.         c = 1;
  577.     else
  578.         c = -1;
  579.     for (;;) {
  580.         if (z->big_car < 0)
  581.             z->big_car &= MASK;
  582.         else {
  583.             z->big_cdr = x->big_cdr;
  584.             vs_reset;
  585.             return(z0);
  586.         }
  587.         x = x->big_cdr;
  588.         z = stretch_big(z, 0);
  589.         z->big_car = x->big_car + c;
  590.         if (x->big_cdr == NULL) {
  591.             if (c>=0&&x->big_car>=0&&z->big_car<0) {
  592.                 z->big_car &= MASK;
  593.                 stretch_big(z, 1);
  594.             } else if (c<0&&x->big_car<0&&z->big_car>=0) {
  595.                 stretch_big(z, -2);
  596.             }
  597.             vs_reset;
  598.             return(z0);
  599.         }
  600.     }
  601. }
  602.  
  603. /*
  604.     Big_times(x0, y0) returns the product
  605.     of non-negative bignum x0 and non-negative bignum y0.
  606.     X0 and y0 should be non-negative.
  607. */
  608. struct bignum *
  609. big_times(x0, y0)
  610. struct bignum *x0, *y0;
  611. {
  612.     struct bignum *x, *y;
  613.     struct bignum *z0, *z1, *z;
  614.     int i, h, l;
  615.     vs_mark;
  616.  
  617. /*    vs_push((object)x0);
  618.     vs_push((object)y0);    */
  619.     y = y0;
  620.     z1 = z0 = (struct bignum *)alloc_object(t_bignum);
  621.     z0->big_car = 0;
  622.     z0->big_cdr = NULL;
  623.     vs_push((object)z0);
  624.  
  625. LOOP1:
  626.     i = y->big_car;
  627.     z = z1;
  628.     x = x0;
  629.     h = 0;
  630.  
  631. LOOP:
  632.     extended_mul(i, x->big_car, h, &h, &l);
  633.     z->big_car += l;
  634.     if (z->big_car < 0) {
  635.         z->big_car &= MASK;
  636.         h++;
  637.     }
  638.     if (x->big_cdr == NULL) {
  639.         while (h > 0) {
  640.             if (z->big_cdr == NULL)
  641.                 z = stretch_big(z, 0);
  642.             else
  643.                 z = z->big_cdr;
  644.             z->big_car += h;
  645.             if (z->big_car < 0) {
  646.                 z->big_car &= MASK;
  647.                 h = 1;
  648.             } else
  649.                 break;
  650.         }
  651.         if (y->big_cdr == NULL) {
  652.             vs_reset;
  653.             return(z0);
  654.         }
  655.         y = y->big_cdr;
  656.         if (z1->big_cdr == NULL)
  657.             z1 = stretch_big(z1, 0);
  658.         else
  659.             z1 = z1->big_cdr;
  660.         goto LOOP1;
  661.     }
  662.     x = x->big_cdr;
  663.     if (z->big_cdr == NULL)
  664.         z = stretch_big(z, 0);
  665.     else
  666.         z = z->big_cdr;
  667.     goto LOOP;
  668. }
  669.  
  670. /*
  671.     Sub_int_big_big(i, x, y) destructively subtracts i*x from y.
  672.     I should be a non-negative int.
  673.     X should be a normalized non-negative bignum.
  674.     Y should be non-negative bignum and should be such that
  675.         y <= i*x.
  676. */
  677. sub_int_big_big(i, x, y)
  678. int i;
  679. struct bignum *x, *y;
  680. {
  681.     int h, l;
  682.  
  683.     h = 0;
  684.     for (;;) {
  685.         extended_mul(i, x->big_car, h, &h, &l);
  686.         y->big_car -= l;
  687.         if (y->big_car < 0) {
  688.             y->big_car &= MASK;
  689.             h++;
  690.         }
  691.         if (x->big_cdr == NULL) {
  692.             while (h > 0) {
  693.                 y = y->big_cdr;
  694.                 y->big_car -= h;
  695.                 if (y->big_car < 0) {
  696.                     y->big_car &= MASK;
  697.                     h = 1;
  698.                 } else
  699.                     break;
  700.             }
  701.             break;
  702.         }
  703.         x = x->big_cdr;
  704.         y = y->big_cdr;
  705.     }
  706. }
  707.  
  708. /*
  709.     Get_standardizing_factor_and_normalize(x)
  710.     returns the standardizing factor of x.
  711.     As a side-effect, x will be normalized.
  712.     X should be a positive bignum.
  713.     If x is multiplied by the standardizing factor,
  714.     the most significant digit of x will be not less than 2**30,
  715.     i.e. the most significant bit of that digit will be set.
  716. */
  717. int
  718. get_standardizing_factor_and_normalize(x)
  719. struct bignum *x;
  720. {
  721.     int i, j;
  722.  
  723.     if (x->big_cdr == NULL) {
  724.         if (x->big_car == 0)
  725.             return(-1);
  726.         for (i = 1, j = x->big_car;  (j *= 2) >= 0;  i *= 2)
  727.             ;
  728.         return(i);
  729.     }
  730.     i = get_standardizing_factor_and_normalize(x->big_cdr);
  731.     if (i < 0) {
  732.         x->big_cdr = NULL;
  733.         if (x->big_car == 0)
  734.             return(-1);
  735.         for (i = 1, j = x->big_car;  (j *= 2) >= 0;  i *= 2)
  736.             ;
  737.         return(i);
  738.     }
  739.     return(i);
  740. }
  741.  
  742. /*
  743.     Div_big_big(x0, y0) divides y0 by x0
  744.     and destructively places the remainder in y0.
  745.     X0 should be a normalized positive bignum,
  746.     whose most significant digit is not less than 2**30.
  747.     Y0 should be a non-negative bignum,
  748.     whose length must be equal to the length of x0
  749.     or one bigger than that.
  750.     Div_big_big(x0, y0) returns the quotient of the division,
  751.     which must be less than 2**31.
  752. */
  753. int
  754. div_big_big(x0, y0)
  755. struct bignum *x0, *y0;
  756. {
  757.     struct bignum *x, *y;
  758.         int q, r;
  759.     
  760.     x = x0;
  761.     y = y0;
  762.     while (x->big_cdr != NULL) {
  763.         x = x->big_cdr;
  764.         y = y->big_cdr;
  765.     }
  766.     if (y->big_cdr != NULL) {
  767.         if (y->big_cdr->big_car >= x->big_car)
  768.             q = MASK-1;
  769.             /*  This is the most critical point.  */
  770.             /*  The long division will fail,  */
  771.             /*  if the quotient can't lie in 31 bits.  */
  772.         else {
  773.             extended_div(x->big_car,
  774.                      y->big_cdr->big_car,
  775.                      y->big_car,
  776.                      &q, &r);
  777.             q -= 2;
  778.             /*  You have to prove that 2 is enough,  */
  779.             /*  by doing elementary arithmetic,  */
  780.             /*  or refer to Knuth's dictionary.  */
  781.         }
  782.     } else
  783.         q = y->big_car/x->big_car - 2;
  784.     if (q <= 0)
  785.         q = 0;
  786.     else
  787.         sub_int_big_big(q, x0, y0);
  788.     while (big_compare(x0, y0) <= 0) {
  789.         q++;
  790.         sub_int_big_big(1, x0, y0);
  791.     }
  792.     return(q);
  793. }
  794.  
  795. int
  796. big_length(x)
  797. struct bignum *x;
  798. {
  799.     int i;
  800.  
  801.     for (i = 1;  x->big_cdr != NULL;  i++, x = x->big_cdr)
  802.         ;
  803.     return(i);
  804. }
  805.  
  806. struct bignum *
  807. big_quotient_remainder_auxiliary(x, y, i)
  808. struct bignum *x, *y;
  809. int i;
  810. {
  811.     struct bignum *q, *qq;
  812.  
  813.     if (i < 0)
  814.         return(NULL);
  815.     if (i == 0) {
  816.         i = div_big_big(y, x);
  817.         if (i == 0)
  818.             return(NULL);
  819.         else {
  820.             qq = (struct bignum *)alloc_object(t_bignum);
  821.             qq->big_car = i;
  822.             qq->big_cdr = NULL;
  823.             return(qq);
  824.         }
  825.     }
  826.     q = big_quotient_remainder_auxiliary(x->big_cdr, y, i-1);
  827.     i = div_big_big(y, x);
  828.     vs_push(((object)q));
  829.     qq = (struct bignum *)alloc_object(t_bignum);
  830.     vs_pop;
  831.     qq->big_car = i;
  832.     qq->big_cdr = q;
  833.     return(qq);
  834. }
  835.  
  836. /*
  837.     Big_quotient_remainder(x0, y0, qp, rp)
  838.     sets the quotient and the remainder of the division of x0 by y0
  839.     to *qp and *rp respectively.
  840.     X0 should be a positive bignum.
  841.     Y0 should be a non-negative bignum.
  842. */
  843. big_quotient_remainder(x0, y0, qp, rp)
  844. struct bignum *x0, *y0, **qp, **rp;
  845. {
  846.     struct bignum *x, *y;
  847.     int i, l, m;
  848.     vs_mark;
  849.  
  850. /*    vs_push((object)x0);
  851.     vs_push((object)y0);    */
  852.     x = copy_big(x0);
  853.     vs_push((object)x);
  854.     y = y0;
  855.     i = get_standardizing_factor_and_normalize(y);
  856.     mul_int_big(i, x);
  857.     mul_int_big(i, y);
  858.     l = big_length(x);
  859.     m = big_length(y);
  860.     *qp = big_quotient_remainder_auxiliary(x, y, l - m);
  861.     if (*qp == NULL) {
  862.         *qp = (struct bignum *)alloc_object(t_bignum);
  863.         (*qp)->big_car = 0;
  864.         (*qp)->big_cdr = NULL;
  865.     }
  866.     div_int_big(i, x);
  867.     div_int_big(i, y);
  868.     *rp = x;
  869.     vs_reset;
  870. }
  871.  
  872. normalize_big(x)
  873. struct bignum *x;
  874. {
  875.     struct bignum *l, *m, *n;
  876.  
  877.     l = NULL;
  878.     m = x;
  879.     for (;;) {
  880.         n = m->big_cdr;
  881.         m->big_cdr = l;
  882.         if (n == NULL)
  883.             break;
  884.         l = m;
  885.         m = n;
  886.     }
  887.     for (;;) {
  888.         if (m->big_cdr == NULL)
  889.             break;
  890.         if (m->big_car == 0)
  891.             m = m->big_cdr;
  892.         else if (m->big_car == -1) {
  893.             m = m->big_cdr;
  894.             m->big_car |= 0x80000000;
  895.         } else
  896.             break;
  897.     }
  898.     l = NULL;
  899.     for (;;) {
  900.         n = m->big_cdr;
  901.         m->big_cdr = l;
  902.         if (n == NULL)
  903.             break;
  904.         l = m;
  905.         m = n;
  906.     }
  907. }
  908.  
  909. /*
  910. normalize_big(x)
  911. struct bignum *x;
  912. {
  913.     if (x->big_cdr == NULL)
  914.         return;
  915.     normalize_big(x->big_cdr);
  916.     if (x->big_cdr->big_cdr == NULL) {
  917.         if (x->big_cdr->big_car == 0)
  918.             x->big_cdr = NULL;
  919.         else if (x->big_cdr->big_car == -1) {
  920.             x->big_car |= ~MASK;
  921.             x->big_cdr = NULL;
  922.         }
  923.     }
  924. }
  925. */
  926.  
  927. object
  928. normalize_big_to_object(x)
  929. struct bignum *x;
  930. {
  931.     normalize_big(x);
  932.     if (x->big_cdr == NULL)
  933.         return(make_fixnum(x->big_car));
  934.     else
  935.         return((object)x);
  936. }
  937.  
  938. double
  939. big_to_double(x)
  940. struct bignum *x;
  941. {
  942.     double d, e;
  943.  
  944.     for (d = 0.0, e = 1.0;  x->big_cdr != NULL;  x = x->big_cdr) {
  945.         d += e * (double)(x->big_car);
  946.         e *= 2.147483648e9;
  947.     }
  948.     d += e * (double)(x->big_car);
  949.     return(d);
  950. }
  951.